#include <iostream>
#include<sys/time.h>
using namespace std;

const long long int num = 10000;
long long int* arr;
int COUNT = 1;//��β���ȡƽ��ֵ
long long int sum = 0;

void init() {
    arr = new long long int[num];
    for (int i = 0; i < num; i++) {
        arr[i] = i;
    }
    sum = 0;
}
void del() {
    delete[]arr;
    sum = 0;
}
//ƽ���㷨
void summing_normal() {
    struct timeval start;
    struct timeval end;
    gettimeofday(&start, NULL);
    for (int c = 0; c < COUNT; c++) {
        sum = 0;
        for (int i = 0; i < num; i++)
            sum += arr[i];
    }
    gettimeofday(&end, NULL);
    cout << "summing_normal_chain:" << ((end.tv_sec - start.tv_sec) * 1000000.0 + (end.tv_usec - start.tv_usec)) * 1.0 / 1000 / COUNT << "ms" << endl;
}
//��·��ʽ
void summing_multi_way_chain() {
    struct timeval start;
    struct timeval end;
    gettimeofday(&start, NULL);
    for (int c = 0; c < COUNT; c++) {
        long long int sum1 = 0, sum2 = 0;
        for (int i = 0; i < num - 1; i += 2) {
            sum1 += arr[i];
            sum2 += arr[i + 1];
        }
        sum = sum1 + sum2;
    }
    gettimeofday(&end, NULL);
    cout << "summing_multi_way_chain:" << ((end.tv_sec - start.tv_sec) * 1000000.0 + (end.tv_usec - start.tv_usec)) * 1.0 / 1000 / COUNT << "ms" << endl;
}
//�ݹ麯��
void summing_recursive(long long int n) {
    if (n == 1) {
        return;
    }
    else {
        for (long long int i = 0; i < n / 2; i++) {
            arr[i] += arr[n - i - 1];
        }
        n = n / 2;
        summing_recursive(n);
    }
}
void summing_recurse() {
    struct timeval start;
    struct timeval end;
    gettimeofday(&start, NULL);
    for (int c = 0; c < COUNT; c++) {
        long long int n = num;
        summing_recursive(n);
    }
    gettimeofday(&end, NULL);
    cout << "summing_recurse:" << ((end.tv_sec - start.tv_sec) * 1000000.0 + (end.tv_usec - start.tv_usec)) * 1.0 / 1000 / COUNT << "ms" << endl;
}
//����ѭ��
void summing_cycles() {
    struct timeval start;
    struct timeval end;
    gettimeofday(&start, NULL);
    for (int c = 0; c < COUNT; c++) {
        long long int m = num;
        for (; m > 1; m /= 2) {
            for (int i = 0; i < m / 2; i++) {
                arr[i] = arr[i * 2] + arr[i * 1 + 1];
            }
        }
    }
    gettimeofday(&end, NULL);
    cout << "summing_double_cycles:" << ((end.tv_sec - start.tv_sec) * 1000000.0 + (end.tv_usec - start.tv_usec)) * 1.0 / 1000 / COUNT << "ms" << endl;
}

int main()
{
    init();
    summing_normal();
    del();

    init();
    summing_multi_way_chain();
    del();

    init();
    summing_recurse();
    del();

    init();
    summing_cycles();
    del();

    return 0;
}